14.5 並列マーキング
概要
マーキングの3要素
ワークリストから処理するオブジェクトを獲得
マークされているかチェックしてマーク
子オブジェクトをワークリストに追加
ワークリストがスレッドローカルであるとする
オブジェクトの獲得は同期なしでOK
スレッドローカルなワークリストが空になったら別スレッド or グローバルのワークリストから盗む
オブジェクトを2回以上マークしたり,子オブジェクトを2回以上ワークリストに入れても,非移動型コレクタならばパフォーマンスに影響するだけでアルゴリズムの正当性に影響しない
マークがオブジェクトヘッダやバイトマップ中のバイトで表現されているなら,不可分でないロードとストア命令でマークをテスト&セットしてよい
data raceがあるから大丈夫じゃないと思う
この本全体でdata raceに対応していない感じがする
2つのスレッドが同じ値を書き込んだとしても、その値が書き込まれることを保証していない
マークがビットマップに保存されていて,他スレッドとビットマップを共有しているなら同期が必要
いろいろ書いてあるけど要は共有するデータ構造は適切な粒度で同期せよという話
リアルタイムGCなら,でかいオブジェクトを分割して扱う仕組みが必要だったりする
子オブジェクトが多いと,キューに追加するのを1つのスレッドが全部やってたら大変
プロセッサ中心のテクニック
ワークスティーリング
Endo らの実装
マーク処理を行う各スレッドに,スレッドローカルなマークスタックと,盗まれるための仕事のキューを用意
generateWork: 定期的に盗まれるためのキューを見て,空ならスレッドローカルなマークスタックの中身を全て移す
acquireWork: アイドルなスレッドは,以下の手順で仕事を盗む
自分の盗まれるキューをみて仕事があったら半分盗む
空だったら,他のスレッドのキューをみて仕事があったら半分盗む
盗むことを表明してから盗まれるキューのロックを獲得し,その後盗むアプローチはロックの獲得のための時間が非効率らしい
ロックしようとして成功したら盗み,失敗したら諦めるようにする(別のキューを探索する)
code:python
shared stealableWorkQueueN # スレッドごとに1つ thread_local myMarkStack
me = myThreadId
def acquireWork():
if not isEmpty(myMarkStack):
return
lock(stealableWorkQueueme) n = size(stealableWorkQueueme) // 2 transfer(stealableWorkQueueme, n, myMarkStack) unlock(stealableWorkQueueme) if isEmpty(myMarkStack):
for j in Threads:
if not locked(stealableWorkQueuej): if lock(stealableWorkQueuej): n = size(stealableWorkQueuej) // 2 transfer(stealableWorkQueuej, n, myMarkStack) unlock(stelableWorkQueuej) return
def performWork():
while pop(myMarkStack, ref):
for fld in Pointers(ref):
child = *fld
if child != null and not isMarked(child):
setMarked(child)
push(myMarkStack, child)
def generateWork():
if isEmpty(stealableWorkQueueme): n = size(markStack)
lock(stealableWorkQueueme) transfer(myMarkStack, n, stealableWorkQueueme) unlock(stealableWorkQueueme) どんな並列コレクタでも,マークビットの扱われ方や,巨大配列の処理のされ方に注意すること
例えばビットマップ使ってるなら不可分にセットしないといけない
ビットマップを使っている場合は,例えば以下のようにする(Endo ら(1997)の手法)
通常のロード命令でビットをテストし,セットされていなければ不可分にセットする
これってC++で言うSingleton patternのdouble checking問題と同じ構造で、現代のプロセッサでは無意味なのではないか
最初の通常のテストによる分岐で不必要な場合は実行されないようにしたつもりだろうが、実際にはout of order実行によって実行されうるので、コストの削減にならない
不可分なセットに失敗したら,再度不可分なセットを試みる
最初のテストを抜けたときのみセットするので,再試行の回数は限られている
code:python
def setMarked(ref):
oldByte = markByte(ref) # 対象のオブジェクトのマークビットが格納されている 1 word の取得?
bitPosition = markBit(ref) # そのワード中の何ビット目か,かな?
while True:
# oldByte = ... はここじゃないか?
if isMarked(oldByte, bitPosition):
return
newByte = mark(oldByte, bitPosition) # そのビットをマークしたときのマスクを計算
if CompareAndSet(&markByte(ref), oldByte, newByte):
return
巨大なポインタ配列の処理の場合,例えばオブジェクトを小さな部分に分割してマークスタックに積むことで,マークスタック溢れを防いだりする
年少世代はコピー方式,年長世代をマークコンパクト方式で管理
ここでは並列マークにのみ焦点を絞る
スレッドごとに固定長の deque を1つずつ用意する
bottom がマークスタック,top が盗まれる仕事の先頭として振る舞う
push に同期は不要,pop/remove には必要
負荷の調整をするときのみ同期の仕組みが活性化するという長所を持つ
c.f. 灰色パケット(あとで議論)などのアプローチでは常に負荷の調整の仕組みが働く
deque が固定長なのであふれることがある
グローバルなオーバーフロー集合を用意
溢れたオブジェクトを管理する
溢れたオブジェクトは型フィールドを使って連結される(図14-2)
クラス毎にオーバヘッドを支払う必要がある
リンクの更新はオブジェクトの型フィールドを(不可分に)更新することになるので,ミューテータが型フィールドに高速にアクセスする必要がある場合,この方法は不適当
実際にあふれた場合は,deque の下半分をオーバーフロー集合に追加
アイドルなスレッドは,他のスレッドから盗む前にオーバーフロー集合から要素を取り出す
オーバーフロー集合の半分の長さ分(あふれるときは多分それ以下)をもらう
code:python
# 14-3 Flood et al の並列マークスイープアルゴリズム
shared overflowSet
me = myThreadId
def acquireWork():
return
n = size(overflowSet) // 2
if transfer(overflowSet, n, dequeme) return
for j in Threads:
if ref != null:
return
def performWork():
while True:
if ref == null:
return
for fld in Pointers(ref):
child = *fld
if child != null and not isMarked(child):
setMarked(child)
if not push(dequeme, child) transfer(dequeme, n, overflowSet) def generateWork():
pass # do nothing
https://gyazo.com/6905fc553910e0b85d9ff413d73f382b
Silbert らの実装
リアルタイム Java VM Jamaica の並列で並行な実行のためのアルゴリズム
Jamaica
オブジェクトを分割してブロックを連結した構造になっている
ブロック単位のマーク時間が有界になる
つまりブロックにはいくつかのフィールドが入ってる?
コレクタはオブジェクトではなくブロックを扱うことになる
(マークスイープの文脈の)色はオブジェクトではなくブロックに割り当てる
そのブロックの走査が完全に終わる前に(黒になる前に)他スレッドが同じブロックを走査してしまうかもしれない
無煙炭色(anthracite)を導入し,ブロックが走査途中である状態を表すようにする
ブロックは白・灰色・無煙炭色・黒の四色
ブロックが白色
まだマーク処理を行っていない
ワークリストに追加されていない
ブロックが灰色
子ブロックが全部白または灰色
ワークリストから取り出されていない
ブロックが無煙炭色
子ブロックが全部白または灰色
ワークリストから取り出されている
直感(?):あるスレッドがそのブロックをまさに走査中
ブロックが黒色
子ブロックが全部白以外
あるスレッドが他スレッドから灰色リストを盗む場合にも,リストの先頭を無煙炭色にする
無煙炭色を用いた仕組みは非常に粗粒度
盗まれるスレッドがGCの仕事をしていない or ライトバリアによってブロックを灰色リストに追加しようとしている程度ならうまく働く
すべてのスレッドがGCをしていれば,灰色ブロックが残った唯一の灰色リストを盗み合うという状況に陥る可能性があるが,実際にはあまり起こらないらしい
フェーズの終了とワークスティーリング
Endo らの方式(初期)
空になったマークスタックと盗まれるための仕事のキューの数を数えるグローバルカウンタを用いる
カウンタの不可分な更新がボトルネックに…
Endo らの方式(Algorithm 13-18)
各プロセッサにマークスタックとキューのそれぞれが空になったことを表すフラグを用意する
フラグはロック無しでセット・クリア可能
あるプロセッサでフェーズの終了を調べる手順
1. グローバルな割り込み検出フラグをクリアし,他の全てのプロセッサの2つのフラグを確認
2. 他のプロセッサによって割り込み検出フラグが再びセットされていないか確認
他のプロセッサは仕事を再開するときには割り込み検出フラグをセット
この方法の場合,プロセッサAがBから盗むときに注意する必要あり
1. A は自分のスタックが空になったことを示すフラグをクリア
2. 次に割り込み検出フラグをセット
3. 最後にBのキューが空になったことを示すフラグをセット
この方式は,2つ以上のスレッドが終了判定しようとするとうまく行かない
1. 終了手順の1で割り込みフラグをクリア
2. 仕事するひとが割り込み検出フラグをセット (盗む手順の2)
3. 別の終了判定スレッドが終了判定の手順1で割り込みフラグをクリア
4. 最初の終了判定スレッドが手順2でフラグのセットを検出しそこねる
Kolodner and Petrank の方式
同時に1つのスレッドだけが終了判定を行うようにロックを導入
ロックには判定スレッドIDという名前の,同期してアクセスされるグローバルワードを使用
終了判定したいときは不可分に ID に書き込むようにする
ここらへんは全部13章でやりました
Flood らの方式
ステータスワードを使う
ステータスワード中の各ビットがそれぞれのスレッドの状態を表す
初期状態は全部 ON
各スレッドは不可分にステータスワードを更新する
各スレッドは自分の担当分の仕事がなくなったらフラグをOFFに
他のスレッドから仕事を盗めるなら,フラグをONにして盗もうとする
盗むのに失敗したら,フラグをOFFにして盗むのを継続する
繰り返しステータスワードを調べながら全てのビットがOFFになるのを待つ
全部オフになったら終了
スレッド数 > ワード長さのときスケールしない
アクティブなスレッド数の数をカウントする (Peter Kessler)
書いてないのでわからないがやり方次第でいい感じになるのかな
Endo らの初期方式となんか違うのか?
灰色パケット
次のひと頑張って~
...